/*
 * Authors: Kyle Tucker, Stephen Herbein, and Ron Lewis
 * Adapted from online material
 * CISC220 Project, Dr. Atlas, Fall 2011
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <cmath>
#include <cstring>
using namespace std;

/*
 * Node class
 * Description:
 * This class contains the information for any given node, including its latitude, longitude, id
 * the node previous to it, and its distance from the start. Notice that the initial distance
 * is set to 100000000, which is the equivalent of infinity for Dijkstra's Algorithm.
 */

class Node
{
public:

	/*
	 * Description:
	 * This is the constructor for this class.
	 */

	Node(int id, double lat, double lon)
	: id(id), previous(NULL), distanceFromStart(10000000), latitude(lat), longitude(lon)
	{
	}

public:
	int id;
	Node* previous;
	double distanceFromStart;
	double latitude;
	double longitude;
};

/*
 * Way class
 * Description:
 * This class contains the information for a way, including its name, type, and the nodes that are contained
 * in the way.
 */

class Way
{
public:
	string name;
	string type;
	vector<Node*> nodeElements;

	/*
	 * Description:
	 * This is the constructor for this class.
	 */

	Way(string id)
	: name(id), type("Empty")
	{
	}
};

/*
 * Edge class
 * Description:
 * This class contains the information pertaining to edges on the graph, including the nodes that define
 * the edge, the distance of the edge, and the way that the edge is on.
 */

class Edge
{
public:

	/*
	 * Description:
	 * This is the constructor for this class.
	 */

	Edge(Node* node1, Node* node2, double distance, Way* currWay)
	: node1(node1), node2(node2), distance(distance), way(currWay), trafficCondition(NULL), incidentSev(10)
	{
	}

	/*
	 * Description:
	 * This method returns true if two nodes are connected to each other.
	 */

	bool Connects(Node* node1, Node* node2)
	{
		return (
				(node1 == this->node1 &&
						node2 == this->node2) ||
						(node1 == this->node2 &&
								node2 == this->node1));
	}
public:
	Node* node1;
	Node* node2;
	double distance;
	Way* way;
	char* trafficCondition;
	int incidentSev;
};

/*
 * TrafficItem class
 * Description:
 * This class contains the information for a single location of traffic. Traffic is specified based upon its
 * latitude, longitude, and the type. The type of traffic can either be red, more severe, or yellow, less severe.
 */

class TrafficItem
{
public:
	char* type;
	double latitude;
	double longitude;

	/*
	 * Description:
	 * This is the constructor for this class.
	 */

	TrafficItem(double lat, double lon, char* typ)
	: latitude(lat), longitude(lon), type(typ)
	{
	}
};

/*
 * IncidentItem class
 * Description:
 * This class contains the information for a location where an incident has occurred. Incidents have a latitude,
 * a longitude, and a severity. Severity is an integer scale ranging from 0-2, 0 being the lowest and 2 the highest.
 */

class IncidentItem
{
public:
	int severity;
	double latitude;
	double longitude;

	/*
	 * Description:
	 * This is the constructor for this class.
	 */

	IncidentItem(double lat, double lon, int sev)
	: latitude(lat), longitude(lon), severity(sev)
	{
	}
};

/*
 * DijkstrasAlgorithm class
 * Description:
 * This class contains all of the information required to produce a graph representing a given location, with
 * traffic and incident data built in.
 */

class DijkstrasAlgorithm
{
public:
	vector<Node*> nodes;
	vector<Edge*> edges;
	vector<Way*> ways;
	vector<TrafficItem*> traffic;
	vector<IncidentItem*> incidents;

	/*
	 * Description:
	 * This is the deconstructor for the class.
	 */

	~DijkstrasAlgorithm(){
		while (!nodes.empty()){
			nodes.pop_back();
		}
		while (!edges.empty()){
			edges.pop_back();
		}
		while (!ways.empty()){
			ways.pop_back();
		}
		while (!traffic.empty()){
			traffic.pop_back();
		}
		while (!incidents.empty()){
			incidents.pop_back();
		}
	}

	/*
	 * Description:
	 * This method performs Dijkstra's Algorithm on the nodes vector starting at the
	 * input node.
	 */

	void Dijkstras(Node * input)
	{
		vector<Node*>* nodesCopy = new vector<Node*>();\
		// create a cope of the nodes vector to perform the algorithm on
		for (int i = 0; i < nodes.size(); i++){
			nodesCopy->push_back(nodes.at(i));
		}
		// set the input node's distance to 0
		input->distanceFromStart = 0;
		// while there are still nodes left to look at
		while (nodesCopy->size() > 0)
		{
			// find the smallest node
			Node* smallest = ExtractSmallest(*nodesCopy);
			// find all nodes adjacent to that node
			vector<Node*>* adjacentNodes =
					AdjacentRemainingNodes(smallest);
			const int size = adjacentNodes->size();
			// step through all of the adjacent nodes
			for (int i=0; i<size; ++i)
			{
				Node* adjacent = adjacentNodes->at(i);
				// get the distance between the adjacent node and the smallest node,
				// and add it to the smallest node's distance
				double distance = Distance(smallest, adjacent) +
						smallest->distanceFromStart;

				// if this distance is less than the adjacent node's already loaded
				// distance
				if (distance < adjacent->distanceFromStart)
				{
					// set its distance to the smaller distance
					adjacent->distanceFromStart = distance;
					// set its previous node to the smallest node
					adjacent->previous = smallest;
				}
			}
			// clean up memory
			delete adjacentNodes;
		}
		delete nodesCopy;
	}

	/*
	 * Description:
	 * This method finds the node with the smallest distance, removes it, and returns it.
	 */

	Node* ExtractSmallest(vector<Node*>& nodes)
	{

		int size = nodes.size();
		// if there are no nodes, return NULL
		if (size == 0){
			return NULL;
		}
		int smallestPosition = 0;
		Node* smallest = nodes.at(0);
		// step through all of the nodes
		for (int i=1; i<size; ++i)
		{
			Node* current = nodes.at(i);
			// if the current node has a smaller distance from the start than than the original,
			// set the smallest to the current and set the smallest position to that position
			if (current->distanceFromStart <
					smallest->distanceFromStart)
			{
				smallest = current;
				smallestPosition = i;
			}
		}
		// remove the smallest node
		nodes.erase(nodes.begin() + smallestPosition);
		return smallest;
	}

	/*
	 * Description:
	 * This method returns all nodes adjacent to 'node' which are still in the nodes vector.
	 */

	vector<Node*>* AdjacentRemainingNodes(Node* node){

		vector<Node*>* adjacentNodes = new vector<Node*>();
		const int size = edges.size();
		// step through every edge
		for(int i=0; i<size; ++i)
		{
			Edge* edge = edges.at(i);
			Node* adjacent = NULL;
			// if the edge's first node is the input
			if (edge->node1 == node)
			{
				// set adjacent to the second node
				adjacent = edge->node2;
			}
			// if the edge's second node is the input
			else if (edge->node2 == node)
			{
				// set adjacent to the first input
				adjacent = edge->node1;
			}
			// if there is an adjacent and it still exists in the nodes vector
			if (adjacent && Contains(nodes, adjacent))
			{
				// add it to the adjacentNodes vector
				adjacentNodes->push_back(adjacent);
			}
		}
		return adjacentNodes;
	}

	/*
	 * Description:
	 * This method returns the distance between two connected nodes.
	 */

	double Distance(Node* node1, Node* node2)
	{
		const int size = edges.size();
		// step through each edge
		for(int i=0; i<size; ++i)
		{
			Edge* edge = edges.at(i);
			// if the nodes are connected
			if (edge->Connects(node1, node2))
			{
				// return the distance between them
				return edge->distance;
			}
		}
		// if they aren't connected, return -1
		// this should never happen
		return -1;
	}

	/*
	 * Description:
	 * This method evaluates if the the 'nodes' vector contain 'node'.
	 */

	bool Contains(vector<Node*>& nodes, Node* node)
	{
		const int size = nodes.size();
		// step through every node
		for(int i=0; i<size; ++i)
		{
			// if the node is equal to the current node in the vector, return true
			if (node == nodes.at(i))
			{
				return true;
			}
		}
		// otherwise, return false
		return false;
	}

	/*
	 * Description:
	 * This method returns the name of the Way(street) that
	 * contains both of the given Nodes. It returns
	 * NULL if no since Way exists.
	 */

	string getStreetName(Node* node1,Node* node2) {

		// Booleans indicating whether or not the first
		// or second Node has been found in the current Way
		bool containsFirst = false;
		bool containsSecond = false;
		// Iterates through all the Ways
		for (int i = 0; i < ways.size(); i++){
			// Iterates through all the Nodes in the current Way
			for (int j = 0; j < ways.at(i)->nodeElements.size(); j++){
				// Triggers if the first Node is found
				if(ways.at(i)->nodeElements.at(j) == node1){
					// Change the Boolean to indicate the first Node has been found
					containsFirst = true;
				}
				// Triggers if the second Node is found
				else if(ways.at(i)->nodeElements.at(j) == node2){
					// Change the Boolean to indicate the second Node has been found
					containsSecond = true;
				}
				// Triggers if both Nodes have been found
				if(containsFirst && containsSecond){
					// Returns the name of the current Way
					return ways.at(i)->name;
				}
			}
			// Resets the Booleans for the next Way
			containsFirst = false;
			containsSecond = false;
		}
		// If all the Ways have been checked, return NULL
		return NULL;

	}

	/*
	 * Description:
	 * This method prints a list of street names representing
	 * the shortest path between the starting point
	 * used for Dijkstra's algorithm and the given
	 * destination.
	 */

	void PrintShortestRouteTo(Node* destination){

		// Holds the current Node being considered
		Node* current = destination;
		// Holds the street names already visited
		stack<string> streets = stack<string>();
		// Holds the next street name to be added to streets
		string nextStreet;
		//Holds the distances for each segment of the trip
		stack<double> distance = stack<double>();
		//Accumulator for the distances
		double accumulator = 0;
		// Continues until the current Node is the starting one
		while (current->previous){
			// Gets the street name of the Way that contains
			// the current Node and the one before it
			nextStreet = getStreetName(current,current->previous);
			if((streets.size() != 0) && (streets.top() != nextStreet)){
        // Add the accum to the distance stack
        distance.push(accumulator);
        //Reset accumulator
        accumulator = 0;
      }
			//Calcs the distances between current Node and the previous
			accumulator = accumulator + Distance(current->previous, current);
			// Triggers if no streets have been added to streets
			// or if the next street is different from the one just added
			if((streets.size() == 0) || (streets.top() != nextStreet)){
				// Push the next street on to streets
				streets.push(nextStreet);
			}
			// Move to the Node before the current one
			current = current->previous;
		}
		distance.push(accumulator);
		// While elements remain in streets
		while(streets.size() != 0){
		  //Print the top element of Distance
		  cout << "Go " << distance.top() << " miles on ";
			// Print the top element of streets
			cout << streets.top() << endl;
			// Pop the top element of streets
			streets.pop();
			// Pop the top element of distance
			distance.pop();
		}
	}

	/*
	 * Description:
	 * This method reads in all of the nodes from a text file containing the node information.
	 */

	void readNodes(){

		string STRING;
		ifstream infile;
		// open the file
		infile.open ("220-Nodes-Final.txt");
		int counter;
		int id = 0;
		double lat = 0;
		double lon = 0;
		// go through every line
		while(!infile.eof())
		{
			// save the line in STRING
			getline(infile,STRING);
			// make STRING into a char array
			char * charArray = new char[STRING.size()+1];
			charArray[STRING.size()]=0;
			memcpy(charArray, STRING.c_str(), STRING.size());
			char * pch;
			// create the first string token, delimited by either a space or a new line
			pch = strtok(charArray, " \n");
			counter = 0;
			// the first token is the id
			id = atoi(pch);
			// got through the char array creating more string tokens
			while(pch != NULL){
				pch = strtok(NULL, " \n");
				// set the next string token to the latitude
				if(counter == 0){
					lat = atof(pch);
				}
				// set the final string token to the longitude
				else if(counter == 1){
					lon = atof(pch);
				}
				counter++;
			}
			// create the node and add it to the node array
			nodes.push_back(new Node(id, lat, lon));
		}
		// close the file
		infile.close();
	}

	/*
	 * Description:
	 * This method reads in all of the ways from the text file containing all of the way information.
	 */

	void readWays(){

		string STRING;
		ifstream infile;
		// open the file
		infile.open ("220-Ways-Final.txt");
		int counter;
		// go through every line
		while(!infile.eof())
		{
			// save the line in STRING
			getline(infile,STRING);
			// make STRING into a char array
			char * charArray = new char[STRING.size()+1];
			charArray[STRING.size()]=0;
			memcpy(charArray, STRING.c_str(), STRING.size());
			char * pch;
			// if the first item in the char array is not a space
			if(!isspace(charArray[0])){
				// create a string token of the way id, delimited by a hyphen or a new line
				pch = strtok(charArray, "-\n");;
				// make a new way with this id
				ways.push_back(new Way(pch));\
				// continue through the char array
				while(pch != NULL){
					pch = strtok(NULL, "-\n");
					// if the way has a name
					if(pch != NULL){
						// set the next string token to it
						ways.back()->name = pch;
					}
				}
			}
			// if the first item is a space
			else{;
			// get the id of the node
			pch = strtok(charArray, "\n");
			// find the node in the nodes vector, and add it to the way's nodeElements
			ways.back()->nodeElements.push_back(findNode(atoi(pch)));
			// if the way has two or more nodes
			if(ways.back()->nodeElements.size() > 1){
				// find the distance between the current and the previous node
				double distance = generateDistance(ways.back()->nodeElements[ways.back()->nodeElements.size()-1],ways.back()->nodeElements[ways.back()->nodeElements.size()-2]);
				// create an edge between them using this distance and add the edge to the edges vector
				edges.push_back(new Edge(ways.back()->nodeElements[ways.back()->nodeElements.size()-1],ways.back()->nodeElements[ways.back()->nodeElements.size()-2], distance, ways.back()));
			}
			}
		}
		// close the file
		infile.close();
	}

	/*
	 * Description:
	 * This method performs binary search on the nodes vector to find the given node. If the node is not found,
	 * it returns NULL.
	 */

	Node * findNode(int id){

		int first = 0;
		int last = nodes.size();

		// for each iteration
		while (first <= last){
			// find the midpoint
			int mid = (first + last)/2;
			// if the input is greater than the midpoint id
			if (id > nodes[mid]->id){
				// retry with a new starting point
				first = mid + 1;
			}
			// if the input is less than the midpoint id
			else if (id < nodes[mid]->id){
				// retry with a new ending point
				last = mid - 1;
			}
			// if the input is equal to the midpoint id, return the midpoint
			else {
				return nodes[mid];
			}
		}

		// if the node is not found, return NULL
		return NULL;
	}

	/*
	 * Description:
	 * This method calculates the distance between two nodes. It uses a known conversion factor to convert
	 * latitudinal and longitudinal degrees into miles.
	 */
	double generateDistance(Node* node1, Node* node2){

		// conversion mathematics to get from degrees to miles
		double ratio = 0.99664719;
		double internal = atan(ratio*tan(node1->latitude));
		// 69 miles/degree of latitude
		double a = (node1->latitude - node2->latitude)*69;
		// complex conversion to miles
		double b = (node1->longitude - node2->longitude)*((atan(1)*4)/180)*6378137*cos(internal)*0.000621371192;
		// pythagorean theorem
		return (sqrt((a*a) + (b*b)));
	}

	/*
	 * Description:
	 * This method sorts an array of nodes by ID in increasing order using Bubble Sort.
	 */

	vector<Node*> sortByID(vector<Node*> nodeArray){

		vector<Node*> sorted;

		// go through the array
		for(int count = 0; count < nodeArray.size() - 1; count++){
			for(int count1 = 0; count1 < nodeArray.size() - count - 1; count1++){
				// if the next node is less than the current one
				if(nodeArray[count1]->id > nodeArray[count1+1]->id){
					// swap
					Node* temp = nodeArray[count1];
					nodeArray[count1] = nodeArray[count1+1];
					nodeArray[count1+1] = temp;
				}
			}
		}

		// put the sorted array in a new array
		for(int count = 0; count < nodeArray.size(); count++){
			sorted.push_back(nodeArray[count]);
		}

		return sorted;
	}

	/*
	 * Description:
	 * This method resolves which edges experience traffic effects and marks them with the effect.
	 */

	vector<Edge*> trafficEffects(){

		vector<Edge*> returnEdges;
		vector<Node*> closest;
		Node * node1 = NULL;
		Node * node2 = NULL;

		// step through all of the traffic data
		for (int count = 0; count < traffic.size(); count++){

			// find the closest array of nodes to the traffic
			closest = getClosest(traffic[count]->latitude, traffic[count]->longitude);

			// step through each node
			for (int index = 1; index < closest.size(); index++){
				// if two nodes are consecutive by ID
				if((closest[index]->id - closest[index-1]->id) <= 5){
					// find the edge that they make up and mark it
					Edge* tempEdge = findEdge(closest[index], closest[index-1]);
					if (tempEdge != NULL){
						if (tempEdge->trafficCondition == NULL){
							tempEdge->trafficCondition = traffic[count]->type;
							returnEdges.push_back(tempEdge);
						}
					}
				}
			}
		}

		return returnEdges;

	}

	/*
	 * Description:
	 * This method resolves which edges experience incidence effects and marks them with the
	 * effect.
	 */

	vector<Edge*> incidentEffects(){

		vector<Edge*> returnEdges;
		vector<Node*> closest;
		Node * node1 = NULL;
		Node * node2 = NULL;

		// step through all of the traffic data
		for (int count = 0; count < incidents.size(); count++){

			// find the closest array of nodes to the traffic
			closest = getClosest(incidents[count]->latitude, incidents[count]->longitude);

			// step through each node
			for (int index = 1; index < closest.size(); index++){
				// if two nodes are consecutive by ID
				if((closest[index]->id - closest[index-1]->id) <= 5){
					// find the edge that they make up and mark it
					Edge* tempEdge = findEdge(closest[index], closest[index-1]);
					if (tempEdge != NULL){
						if (tempEdge->incidentSev == 10){
							tempEdge->incidentSev = incidents[count]->severity;
							returnEdges.push_back(tempEdge);
						}
					}
				}
			}
		}

		return returnEdges;

	}

	/*
	 * Description:
	 * This method finds the edge that two nodes make up, if any. If the nodes do not make an
	 * edge, it returns NULL.
	 */

	Edge* findEdge(Node* node1, Node* node2){

		// step through the edges
		for (int count = 0; count < edges.size(); count++){

			// if the edge's nodes are node1 and node2, return it
			if((edges[count]->node1->id == node1->id &&
					edges[count]->node2->id == node2->id) ||
					(edges[count]->node1->id == node2->id &&
							edges[count]->node2->id == node1->id)){
				return edges[count];
			}
		}

		return NULL;
	}

	/*
	 * Description:
	 * This method finds the set of five nodes closest to the latitude and longitude input.
	 */

	vector<Node*> getClosest(double latitude, double longitude){


		Node* tmpNode = new Node(1, latitude, longitude);
		double temp;
		double firstDistance = generateDistance(tmpNode, nodes[0]);
		Node* firstNode = nodes[0];
		double secondDistance = generateDistance(tmpNode, nodes[1]);
		Node* secondNode = nodes[1];
		double thirdDistance = generateDistance(tmpNode, nodes[2]);
		Node* thirdNode = nodes[2];
		double fourthDistance = generateDistance(tmpNode, nodes[3]);
		Node* fourthNode = nodes[3];
		double fifthDistance = generateDistance(tmpNode, nodes[4]);
		Node* fifthNode = nodes[4];
		vector<Node*> closest;

		// for every node
		for (int count = 5; count < nodes.size(); count++){

			// calculate the distance from the node to the inputs
			temp = generateDistance(tmpNode, nodes[count]);
			// if this distance is less than the first element, replace it and shift the others
			if (temp < firstDistance){
				fifthNode = fourthNode;
				fifthDistance = fourthDistance;
				fourthNode = thirdNode;
				fourthDistance = thirdDistance;
				thirdNode = secondNode;
				thirdDistance = secondDistance;
				secondNode = firstNode;
				secondDistance = firstDistance;
				firstNode = nodes[count];
				firstDistance = temp;
			}
			// if this distance is less than the second element, replace it and shift the others
			else if(temp < secondDistance){
				fifthNode = fourthNode;
				fifthDistance = fourthDistance;
				fourthNode = thirdNode;
				fourthDistance = thirdDistance;
				thirdNode = secondNode;
				thirdDistance = secondDistance;
				secondNode = nodes[count];
				secondDistance = temp;
			}
			// if this distance is less than the third element, replace it and shift the others
			else if(temp < thirdDistance){
				fifthNode = fourthNode;
				fifthDistance = fourthDistance;
				fourthNode = thirdNode;
				fourthDistance = thirdDistance;
				thirdNode = nodes[count];
				thirdDistance = temp;
			}
			// if this distance is less than the fourth element, replace it and shift the others
			else if(temp < fourthDistance){
				fifthNode = fourthNode;
				fifthDistance = fourthDistance;
				fourthNode = nodes[count];
				fourthDistance = temp;
			}
			// if this distance is less than the fifth element, replace it and shift the others
			else if(temp < fifthDistance){
				fifthNode = nodes[count];
				fifthDistance = temp;
			}

		}

		// add these nodes to the closest array
		closest.push_back(firstNode);
		closest.push_back(secondNode);
		closest.push_back(thirdNode);
		closest.push_back(fourthNode);
		closest.push_back(fifthNode);

		// sort the array
		closest = sortByID(closest);

		// clean up memory
		delete tmpNode;
		return closest;
	}

	/*
	 * Description:
	 * This method returns the Node closest to the given latitude and longitude.
	 */

	Node* getNode(double latitude,double longitude){

		// Holds the minimum distance from the given point found
		// 10000000.0 is an arbitrarily large starting value
		double minDistance = 10000000.0;
		// Holds the distance of the current Node from the given point
		double distance = 0.0;
		// Holds the closest Node from the given point
		Node* minNode;
		// Holds the current Node
		Node* curr;
		// Iterates through every Node
		for(int i = 0; i < nodes.size(); i++){
			// Gets the current Node
			curr = nodes.at(i);
			// Calculates its distance from the given point
			distance = sqrt(pow(curr->latitude-latitude,2) + pow(curr->longitude-longitude,2));
			// Triggers if the current distance is less than the minimum one
			if(distance < minDistance){
				// Sets the current Node as the new minimum one
				minNode = curr;
				// Sets the current distance as the new minimum distance
				minDistance = distance;
			}
		}
		// Returns the closest Node found
		return minNode;

	}

	/*
	 * Description:
	 * This method returns the inputed latitudes and longitudes.
	 */

	double* getInputs(){

		// Holds the input latitudes and longitudes
		double* inputs = new double[4];
		// Reads in the input latitudes and longitudes
		char currData[20];
		// Counter to hold position in the array
		int counter = 0;
		// Holds a line of the text file
		string line;
		// Holds the text file to be read in
		ifstream textFile;
		// Opens the text file
		textFile.open("inputs.txt");
		// Triggers if the text file opens properly
		if(textFile.is_open()){
			// Continues until the end of the file is reached
			while(textFile.good()){
				// Gets a line of the file
				getline(textFile,line);
				// Iterator for moving through the line
				string::iterator it;
				// Sets the iterator to the beginning of the line
				it = line.begin();
				// Continues until the end of the line is reached
				while(it < line.end()){
					// Continues until comma is found
					while(*it != ','){
						// Adds the current character to the char array
						currData[counter] = *it;
						// Moves the iterator forward
						it++;
						// Increments the count
						counter++;
					}
					// Converts the current char array into a double
					inputs[0] = strtod(currData,NULL);
					// Resets the char array
					for(int i = 0; i < counter; i++){
						currData[counter] = 0;
					}
					// Moves the iterator forward
					it++;
					// Resets the count
					counter = 0;
					// Continues until a colon is found
					while(*it != ':'){
						// Adds the current character to the char array
						currData[counter] = *it;
						// Moves the iterator forward
						it++;
						// Increments the count
						counter++;
					}
					// Converts the current char array into a double
					inputs[1] = strtod(currData,NULL);
					// Resets the char array
					for(int i = 0; i < counter; i++){
						currData[counter] = 0;
					}
					// Moves the iterator forward
					it++;
					// Resets the count
					counter = 0;
					// Continues until a semi-colon is found
					while(*it != ';'){
						// Adds the current character to the char array
						currData[counter] = *it;
						// Moves the iterator forward
						it++;
						// Increments the count
						counter++;
					}
					// Converts the current char array to a double
					inputs[2] = strtod(currData,NULL);
					// Resets the char array
					for(int i = 0; i < counter; i++){
						currData[counter] = 0;
					}
					// Moves the iterator forward
					it++;
					// Resets the count
					counter = 0;
					// Continues until a question mark is found
					while(*it != '?'){
						// Adds the current character to the char array
						currData[counter] = *it;
						// Moves the iterator forward
						it++;
						// Increments the count
						counter++;
					}
					// Moves the iterator forward
					it++;
					// Converts the current char array to a double
					inputs[3] = strtod(currData,NULL);
				}
			}
		}
		else{
			// Indicate that the opening of the file failed
			cout << "Unable to open file" << endl;
		}
		// Return a pointer to the double array containing the inputs
		return inputs;

	}

	/*
	 * Description:
	 * This method reads in the traffic data from a text file and stores it in the traffic vector
	 */

	void getTraffic(){

		vector<double> * bounds = findBounds();
		// Holds the text file being read in
		ifstream textFile;
		// Holds the x coordinate of the current color
		char x[3];
		// Holds the y coordinate of the current color
		char y[3];
		// Holds a line of the text file
		string line;
		// Holds the current position in x or y array
		int counter = 0;
		// Opens the text file
		textFile.open("trafficData.txt");
		// Triggers if the text file opened properly
		if(textFile.is_open()){
			// Continues until the end of the text file is reached
			while(textFile.good()){
				// Gets a line of the file
				getline(textFile,line);
				// An iterator to move through the line
				string::iterator it;
				// Sets the iterator to the beginning of the line
				it = line.begin();
				// Continues until the end of the line is reached
				while(it < line.end()){
					// Triggers if the current color is Red
					if(*it == 'R'){
						// Moves past the color
						it +=2;
						// Continues until a comma is found
						while(*it != ','){
							// Stores the current character
							x[counter] = *it;
							// Moves the iterator forward
							it++;
							// Increments the count
							counter++;
						}
						// Resets the count
						counter = 0;
						// Moves the iterator forward
						it++;
						// Continues until a semicolon is found
						while(*it != ';'){
							// Stores the current character
							y[counter] = *it;
							// Moves the iterator forward
							it++;
							// Increments the count
							counter++;
						}
						// Hard-coded numbers represent the latitude and longitude bounds of the traffic image
						// y is divided by 1000 to account for the 3 digits of x that are added to the end of it
						// when atoi is called
						// The data is stored in a vector of trafficItems
						double lat = 39.895141454269904 + ((atoi(x)) * ((39.47240056379552 - 39.895141454269904) / 400.0));
						double lon = -76.02414541814844 + ((atoi(y) / 1000) * ((-75.47482901192038 + 76.02414541814844) / 400.0));
						// If the latitude and longitude are within the bounds
						if (lat >= bounds->at(0) &&
								lat <= bounds->at(1) &&
								abs(lon) >= abs(bounds->at(2)) &&
								abs(lon) <= abs(bounds->at(3))){
							traffic.push_back(new TrafficItem(lat, lon, "R"));
						}
						// Moves the iterator forward
						it++;
						// Resets the count
						counter = 0;
					}
					// Triggers if the current color is yellow
					else if(*it == 'Y'){
						// Moves the iterator past the color
						it += 2;
						// Continues until a comma is found
						while(*it != ','){
							// Stores the current character
							x[counter] = *it;
							// Moves the iterator forward
							it++;
							// Increments the count
							counter++;
						}
						// Moves the iterator forward
						it++;
						// Increments the count
						counter = 0;
						// Continues until a semi-colon is found
						while(*it != ';'){
							// Stores the current character
							y[counter] = *it;
							// Moves the iterator forward
							it++;
							// Increments the count
							counter++;
						}
						// Hard-coded numbers represent the latitude and longitude bounds of the traffic image
						// y is divided by 1000 to account for the 3 digits of x that are added to the end of it
						// when atoi is called
						// The data is stored in a vector of trafficItems
						double lat = 39.895141454269904 + ((atoi(x)) * ((39.47240056379552 - 39.895141454269904) / 400.0));
						double lon = -76.02414541814844 + ((atoi(y) / 1000) * ((-75.47482901192038 + 76.02414541814844) / 400.0));
						// If the latitude and longitude are within the bounds
						if (lat >= bounds->at(0) &&
								lat <= bounds->at(1) &&
								abs(lon) >= abs(bounds->at(2)) &&
								abs(lon) <= abs(bounds->at(3))){
							traffic.push_back(new TrafficItem(lat, lon, "Y"));
						}
						// Moves the iterator forward
						it++;
						// Increments the count
						counter = 0;
					}
				}
			}
			// Closes the text file
			textFile.close();
		}
		// Triggers if the text file does not open properly
		else{
			// Indicate that the opening of the file failed
			cout << "Unable to open file" << endl;
		}
		delete bounds;
	}

	/*
	 * Description:
	 * This method reads in the incident data from a text file and stores it in the incidents vector
	 */

	void getIncidents(){

		vector<double> * bounds = findBounds();
		// Holds the text file being read in
		ifstream textFile;
		// Holds the latitude value
		string lat = "";
		// Holds the longitude value
		string lon = "";
		// Holds the severity value
		string sev = "";
		// Holds a line of the text file
		string line;
		// Opens the text file
		textFile.open("incidentData.txt");
		// Triggers if the text file opens properly
		if(textFile.is_open()){
			// Continues until the end of the file is reached
			while(textFile.good()){
				// Gets a line of the file
				getline(textFile,line);
				// Iterator for moving through the line
				string::iterator it;
				// Sets the iterator to the beginning of the line
				it = line.begin();
				// Continues until the end of the line is reached
				while(it < line.end()){
					// Continues until a comma is found
					while(*it != ','){
						// Adds the character to the longitude string
						lon.push_back(*it);
						// Moves the iterator forward
						it++;
					}
					// Moves the iterator forward
					it++;
					// Continues until a colon is found
					while(*it != ':'){
						// Adds the character to the latitude string
						lat.push_back(*it);
						// Moves the iterator forward
						it++;
					}
					// Moves the iterator forward
					it++;
					// Continues until a semi-colon is found
					while(*it != ';'){
						// Adds the character to the severity string
						sev.push_back(*it);
						// Moves the iterator forward
						it++;
					}
					// Moves the iterator forward
					it++;
					//cout << lat << "," << lon << "," << sev << endl;
					double latitude = atof(lat.c_str());
					double longitude = atof(lon.c_str());
					// If the latitude and longitude are within the bounds
					if (latitude >= bounds->at(0) &&
							latitude <= bounds->at(1) &&
							abs(longitude) >= abs(bounds->at(2)) &&
							abs(longitude) <= abs(bounds->at(3))){
						incidents.push_back(new IncidentItem(latitude, longitude, atoi(sev.c_str())));
					}
					// Resets the string values
					lat = "";
					lon = "";
					sev = "";
				}
			}
			// Closes the text file
			textFile.close();
		}
		// Triggers if the text file fails to open properly
		else{
			// Indicates the text file did not open properly
			cout << "Unable to open file" << endl;
		}
		delete bounds;

	}

	/*
	 * Description:
	 * This method determines the bounds for the region in terms of min and max longitude
	 * and latitude.
	 * The output bounds vector has four elements in the order of:
	 * minLat, maxLat, minLon, maxLon
	 */

	vector<double> * findBounds(){

		vector<double> * bounds = new vector<double>(4);

		double minLat = nodes[0]->latitude;
		double maxLat = nodes[0]->latitude;
		double minLon = nodes[0]->longitude;
		double maxLon = nodes[0]->longitude;

		// step through each node
		for(int count = 1; count < nodes.size(); count++){

			// if this node is greater than or less than any of the specified values,
			// change the value to the new node's data
			if (nodes[count]->latitude < minLat){
				minLat = nodes[count]->latitude;
			}
			if (nodes[count]->latitude > maxLat){
				maxLat = nodes[count]->latitude;
			}
			if (abs(nodes[count]->longitude) < abs(minLon)){
				minLon = nodes[count]->longitude;
			}
			if (abs(nodes[count]->longitude) > abs(maxLon)){
				maxLon = nodes[count]->longitude;
			}
		}

		// add these values to the bounds vector
		bounds->at(0) = minLat;
		bounds->at(1) = maxLat;
		bounds->at(2) = minLon;
		bounds->at(3) = maxLon;

		return bounds;
	}

	/*
	 * Description:
	 * This method goes through each edge and updates their distance using modifiers for incidents
	 * and traffic
	 * Traffic:
	 * Red: 4x modifier
	 * Yellow: 3/2x modifier
	 * Incidents:
	 * 0 severity: 4/3x modifier
	 * 1 severity: 5/3x modifier
	 * 2 severity: 2x modifier
	 */
	void updateEdges(){

		// if there is traffic data
		if (traffic.size() > 0){

			// find the traffic effects
			vector<Edge*> edges1 = trafficEffects();

			cout << "There are " << edges1.size() << " traffic issues in Newark, DE." << endl;

			// for every edge
			for (int count = 0; count < edges1.size(); count++){

				// modify the distance based upon traffic condition
				if (strcmp(edges1[count]->trafficCondition, "R") == 0){

					edges1[count]->distance = edges1[count]->distance*4;
				}
				else if (strcmp(edges1[count]->trafficCondition, "Y") == 0){

					edges1[count]->distance = edges1[count]->distance*3/2;
				}
			}
		}

		// if there is incident data
		if (incidents.size() > 0){

			// find the incident effects
			vector<Edge*> edges2 = incidentEffects();

			cout << "There are " << edges2.size() << " incidents in Newark, DE." << endl;

			// for every edge
			for (int count = 0; count < edges2.size(); count++){

				// modify the distance based upon the incident condition
				if (edges2[count]->incidentSev == 0){

					edges2[count]->distance = edges2[count]->distance*4/3;
				}
				else if (edges2[count]->incidentSev == 1){

					edges2[count]->distance = edges2[count]->distance*5/3;
				}
				else if (edges2[count]->incidentSev == 2){

					edges2[count]->distance = edges2[count]->distance*2;
				}
			}
		}
	}
};

/*
 * Description:
 * This is the main function for this file.
 */

int main(int argc, char* argv[]){

	// Holds the inputed latitudes and longitudes
	double* inputs;
	// Holds a pointer to the Node at the given latitude and longitude
	Node* inputNode;
	// Creates an object that will hold graph information
	DijkstrasAlgorithm * dA = new DijkstrasAlgorithm();
	// Reads the inputs in
	inputs = dA->getInputs();
	// Read in the Nodes of the graph
	dA->readNodes();
	// Read in the Ways of the graph
	dA->readWays();
	// Read in the traffic data
	dA->getTraffic();
	// Read in the accident/construction data
	dA->getIncidents();
	// Update the Edges to include the traffic/incident data
	dA->updateEdges();
	// Gets the starting Node based on the inputed latitude and longitude
	inputNode = dA->getNode(inputs[0],inputs[1]);
	// Run Dijkstras algorithm with the inputed starting Node
	dA->Dijkstras(inputNode);

	// Gets the starting Node based on the inputed latitude and longitude
	inputNode = dA->getNode(inputs[2],inputs[3]);
	// Display the shortest path to the inputed ending Node
	dA->PrintShortestRouteTo(inputNode);

	// Clean up memory
	delete inputs;
	delete dA;

	return 0;

}
